Algorithms for Routing of Unmanned Aerial Vehicles with Mobile Recharging Stations

摘要

We study the problem of planning a tour for an energy-limited Unmanned AerialVehicle (UAV) to visit a set of sites in the least amount of time. We envisionscenarios where the UAV can be recharged along the way either by landing onstationary recharging stations or on Unmanned Ground Vehicles (UGVs) acting asmobile recharging stations. This leads to a new variant of the TravelingSalesperson Problem (TSP) with mobile recharging stations. We present analgorithm that finds not only the order in which to visit the sites but alsowhen and where to land on the charging stations to recharge. Our algorithmplans tours for the UGVs as well as determines best locations to placestationary charging stations. While the problems we study are NP-Hard, wepresent a practical solution using Generalized TSP that finds the optimalsolution. If the UGVs are slower, the algorithm also finds the minimum numberof UGVs required to support the UAV mission such that the UAV is not requiredto wait for the UGV. Our simulation results show that the running time isacceptable for reasonably sized instances in practice.